package code.D1216;

import java.util.Arrays;

/**
 * author : yeswater
 * date : 2023/12/16
 * 
 * 多数元素
 * 
 */

public class T169 {
    public int majorityElement1(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
    
    // 摩尔投票法
    public int majorityElement(int[] nums) {
        int x = 0, votes = 0; // x 众数 vote 票数
        for (int num : nums) {
            if (votes == 0) {
                x = num;
            }
            votes += num == x ? 1 : -1;
        }
        return x;
    }
}
